package demo2;

public class Sort {
    //归并排序
    public void mergeSort(int[] array) {
        mergeSort(array,0,array.length - 1);
    }
    public void mergeSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        mergeSort(array,start,mid);
        mergeSort(array,mid+1,end);
        merge(array,start,mid,end);
    }
    public void merge(int[] array, int start, int mid, int end) {
        int s1 = start;
        int s2 = mid + 1;
        int k = 0;
        int[] tmp = new int[end - start + 1];
        while ((s1 <= mid) && (s2 <= end)) {
            if (array[s1] > array[s2]) {
                tmp[k++] = array[s2++];
            } else {
                tmp[k++] = array[s1++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {
            tmp[k++] = array[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            array[i + start] = tmp[i];
        }
    }
    //计数排序
    public static void coutingSort (int[] array) {
        int maxVal = array[0];
        int minVal = array[0];

        for (int i = 0; i < array.length; i++) {
            if (array[i] > maxVal) {
                maxVal = array[i];
            }
            if (array[i] < minVal) {
                minVal = array[i];
            }
        }
        int[] count = new int[maxVal - minVal + 1];

        for (int i = 0; i < array.length; i++) {
            int index = array[i];
            count[index - minVal]++;
        }
        //再把临时数组里面的值返回给array
        int k = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                array[k++] = i + minVal;
                count[i]--;
            }
        }
    }



}
